//尼姆博弈
//nim_game.cpp

//A和B轮流从n堆物品中取一些物品
//每次从其中一堆中取至少1个物品，多则不限，最后取光n堆物品的人获胜

//1)局势
//最终局势，最终态：
//A面临(0, 0, ..., 0)(n个零)，必然输
//称(0, 0, ..., 0)(n个零)是最终局势(Terminal Position)，也称最终态，面临此局势者输
//奇异局势，必败态：
//称最终会令自己面临最终局势的局势是奇异局势(Cold Position)
//也称P-Position，必败态
//非奇异局势，必胜态：
//称最终会令对方面临最终局势的局势是非奇异局势(Hot Position)
//也称N-Position，必胜态
//
//2)状态转化
//面临必胜态N时，必然存在一种取法使对方面临必败态P，从而最终获胜
//面临必败态P时，无论怎么取对方都将面临必胜态N，从而最终获败
//当n = 3时，即有3堆物品时
//A面临(0, 0, 0)最终态，必然输
//A面临(0, 1, 1)局势，必须从两堆的其中一堆取至少1个物品
//则B面临(0, 1, 0)或(0, 0, 1)局势，B取一个则A必然输
//因此(0, 1, 1)是一个必败态
//进一步推广，对于n堆物品
//A面临(0, 0, ..., 0, 1, 1)，前面n-2个为0，最后2个为1
//A也必然输，因此该状态也是一个必败态
//
//3)尼姆博弈的求解
//定理：
//对于尼姆博弈中的局势(a1, a2, ..., an)，设@是异或运算(相同为0，相异为1)
//该局势是必败态P当且仅当a1 @ a2 @ ... @ an = 0
//该局势是必胜态N当且仅当a1 @ a2 @ ... @ an != 0
//当面对必胜态N时，需要找出一种方法使减少当前局势中一个数字
//使对面面临必败态P
//设a1 @ a2 @ ... @ an = k
//则局势存在这样的i，使得第i堆物品ai，它的二进制表示上第k位数字一定是1
//只需要将ai上第k位的1改变为0，即可使局势的异或值为0
//即使ai = ai @ k，而且一定存在这样的ai使ai @ k < ai成立，符合减小的规则
//因此对于a1 @ a2 @ ... @ an = k
//找出一个二进制表示中第k位为1的堆ai，并且满足ai @ k < ai
//从中取ai - ai @ k，是ai = ai @ k即可

#include "general_head.h"

bool nim_game(int *a, int n, int& idx, int& get)
{//a为n堆物品，下标从0到n-1
 //判断是否有胜算，若有胜算则返回取的堆的下标号以及取物品的数量，存储于idx和get中
	int k(0);
	for(int i = 0; i < n; ++ i)
		k ^= a[i];
	if(k == 0)
		//若n堆物品的异或值为0，直接认输
		return(false);

	for(int i = 0; i < n; ++ i)
		if((k ^ a[i]) > 0 && (k ^ a[i]) < a[i]){
			//异或运算必须加括号以保证优先级
			//异或值必须大于0，以保证取的物品数不为负数
			//异或值必须小于a[i]，以保证取物品之后该堆物品数不会变成负数
			idx = i;
			get = a[i] - (k ^ a[i]);
			return(true);
		}
	return(false);
}
